rm(list = ls())
library(data.table)
library(foreign)
library(kernlab)
library(MASS)  # for mvrnorm
library(ggplot2)

Attaching package: ‘ggplot2’

The following object is masked from ‘package:kernlab’:

    alpha
library(gridExtra)
library(glmnet)
Loading required package: Matrix
Loading required package: foreach
Loaded glmnet 2.0-16
library(caret)
package ‘caret’ was built under R version 3.5.2
setwd('~/github/bdr/')

Overview

Bayesian distribution regression (BDR) is built on a few pieces of theory:

  1. Kernel mean embeddings
  2. Gaussian process regression (as the prior for the kernel mean embeddings)
  3. Landmark points for dimensionality reduction (advantages of this over FastFood? both are reducing the dimensionality of the feature embedding so that we can calualate the empirical mean)

This notebook builds the theory of Bayesian Distribution Regression piece by piece:

  1. Explore kernels from the kernlab package. We’ll later use the functions from this package to calculate mean embeddings for bags of observations \(\{x_j^i\}_{j=1}^{N_i}\).

Explore Kernels from kernlab package

## create a RBF kernel function with sigma hyper-parameter 0.05
rbf = rbfdot(sigma = 1)
## create artificial data set
x <- matrix(rnorm(60), 6, 10)
## compute kernel matrix
kx <- kernelMatrix(rbf, x)  ## k_12 is equivalent to exp(- sum((x[1,] - x[2,])^2))

Basic Gaussian process

A Gaussian process is a collection of random variables, any finite subset of which follows a multivariate normal distribution

prior: \(f \sim \mathcal{GP}(\mathbf{0}, k(x, x'))\)

We fix a finite set of \(d\) points \(\mathbf{s} = (s_1, \dots, s_d)\) in order to draw from the GP as a multivariate normal. Conditioning on \(s\), this becomes \(\mathbf{f} \sim \mathcal{N}(\mathbf{0}_d, \Sigma_d)\) where \(\Sigma_d\) is the empirical covariance matrix of our points \(s\).

We then ``observe" 5 points \(\{x_i, y_i\}_{i = 1}^n\). We assume that y is observed without noise such that \(y = f(x)\). In order to predict at a new point \(x_\star\), we condiditon on the observed points \(X\) and their associated outcomes \(Y\), and arrive at the closed-form posterior predictive distribution of \(f_\star\)

posterior: \(f_\star | x_\star, X, \mathbf{y} \sim \mathcal{N}(k_\star K^{-1}\mathbf{y}, k_{\star\star} - k_\star K^{-1}k_\star^T)\)

where \(K_{ij} = k(x_i, x_j)\) and \(k_\star = [k(x_1, x_\star), \dots, k(x_n, x_\star)]\) and \(k_{\star\star} = k(x_star, x_star)\)

# define function to calculate empirical covariance matrix based on Gaussian kernel with length-scale l
calcSigma = function(x1, x2, l = 1){
  Sigma = matrix(nrow = length(x1), ncol = length(x2))
  
  for(i in 1:length(x1)){
    for(j in 1:length(x2)){
      Sigma[i,j] = exp(-1/2 * ((x1[i] - x2[j])/l)^2)
    }
  }
  return(Sigma)
}
# define the points that we want to fix for the function draw
s = seq(-5, 5, by = 0.1)
# calculate the empirical covariance of the points (basically 0)
Sigma = calcSigma(s, s)
# draw 5 samples from the GP prior at the fixed points
x_prior = t(mvrnorm(n = 5, mu = rep(0, length(s)), Sigma = Sigma))
x_draws = data.frame(cbind(s, x_prior))
x_draws = melt(x_draws, id = 's', value.name = 'f(x)')
# plot draws from the prior
plot_gp_prior = ggplot(x_draws, aes(x = s, y = `f(x)`, color = variable)) + geom_line() +
  ggtitle("Draws from GP Prior") + theme_minimal()
# specify points that we observe
x_obs = c(-4, -2.5, -1, 0, 4)
y_obs = c(-2, 0, 1, 2, -1)
# calculate kernel matricies needed for posterior evaluation
K_xx = calcSigma(x_obs, x_obs)
K_xstarx = calcSigma(s, x_obs)
K_xxstar = calcSigma(x_obs, s)
K_xstarxstar = calcSigma(s, s)
# calculate posterior mean and variance
mu = K_xstarx %*% solve(K_xx) %*% y_obs
Sigma_star = K_xstarxstar - K_xstarx %*% solve(K_xx) %*% K_xxstar
# draw 5 samples from the posterior at fixed eval points s
x_post = t(mvrnorm(5, mu = mu, Sigma = Sigma_star))
x_post = data.frame(cbind(s, x_post))
x_post = melt(x_post, id = 's', value.name = 'f_star')
# calculate 95% confidence bands for posterior
f_star_covar = data.frame(cbind(s, ub = mu + 2 * sqrt(diag(Sigma_star)), lb = mu - 2 * sqrt(diag(Sigma_star))))
NaNs producedNaNs produced
# plot draws from posterior
plot_gp_post = ggplot() + 
  geom_ribbon(data = f_star_covar, aes(x = s, ymin = V3, ymax = V2), fill = "grey", alpha = 0.5) +
  geom_line(data = x_post, aes(x = s, y = f_star, color = variable)) +
  #geom_point(aes(x = x_obs, y = y_obs)) +
  ggtitle("Draws from GP Posterior") +
  theme_minimal()
  
grid.arrange(plot_gp_prior, plot_gp_post, nrow = 1)

Try out BDR on survey data

Goal: Estimate individual-level support using BDR on state-level support outcomes

Data

data_sept18 = data.table(read.spss('data/Sept18/Sept18 public.sav', to.data.frame = T), stringsAsFactors = F)
Undeclared level(s) 2, 3, 4 added in variable: densityUndeclared level(s) 2, 3, 4 added in variable: sdensityUndeclared level(s) 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95 added in variable: ageUndeclared level(s) 1, 2, 3, 4, 5, 6, 7 added in variable: hh1Undeclared level(s) 1, 2, 3, 4, 5, 6, 7 added in variable: hh3
data_sept18

Individual-level survey responses (n = nrow(data_sept18) from September 2018 Pew Research survey (https://www.people-press.org/dataset/september-2018-political-survey/).

Recode survey responses

Recode the survey responses - combine q7 (strong) and q8 (leaners) to get full support response

## support 
data_sept18[, .N, .(q7, q8)]
data_sept18[, qsupport := NULL]
Adding new column 'qsupport' then assigning NULL (deleting it).
data_sept18[q7 == "Democratic Party's candidate" | q8 == "Democratic Party's candidate", qsupport := '1-D']
data_sept18[q7 == "Republican Party's candidate" | q8 == "Republican Party's candidate", qsupport := '2-R']
data_sept18[q8 == "(VOL) Other", qsupport := '3-O']
data_sept18[is.na(qsupport), qsupport := '4-DK/R']
data_sept18[, .(.N, pct = .N/nrow(data_sept18)), qsupport][order(qsupport)]

calculate percentages by state

data_state = data_sept18[, .(y_dem = mean(qsupport == '1-D')
                             , y_rep = mean(qsupport == '2-R')
                             , y_other = mean(qsupport == '3-O')
                             , y_dkr = mean(qsupport == '4-DK/R')
                             , total_respondents = .N
                             # sample covariates
                             , age_under30 = mean(as.numeric(age) < 30)
                             , race_W = mean(racecmb == 'White')
                             ), by = sstate][order(sstate)]
head(data_state)

Check relationshhip between dem vote and % white by state

plot(y_dem ~ race_W
  , data = data_state
)

data_sept18[, .N, hh1][order(hh1)]
X = data_sept18[, .(state = as.character(sstate)
                    , sex_male = as.numeric(sex == 'Male')
                    , sex_female = as.numeric(sex == 'Female')
                    , age = as.numeric(age)
                    
                    , educ_postgrad = as.numeric(grepl("Postgraduate", educ))
                    , educ_bach = as.numeric(grepl("Four year", educ))
                    , educ_assoc = as.numeric(grepl("Two year associate|Sone college", educ))
                    , educ_highschool = as.numeric(grepl("High school graduate", educ))
                    , educ_none = as.numeric(grepl("Less than high school|High school incomplete", educ))
                    
                    , hisp = as.numeric(hisp == 'Yes')
                    , race_white = as.numeric(racecmb == 'White')
                    , race_black = as.numeric(racecmb == 'Black or African-American')
                    , race_asian = as.numeric(racecmb == 'Asian or Asian-American')
                    , race_mixedother = as.numeric(racecmb == 'Mixed Race' | racecmb == 'Or some other race')
                    
                    , relig_protestant = as.numeric(grepl("Protestant|Christian", relig))
                    , relig_catholic = as.numeric(grepl("Catholic", relig))
                    , relig_athiest = as.numeric(grepl("Athiest|Agnostic", relig))
                    , relig_jewish = as.numeric(grepl("Jewish", relig))
                    , relig_muslim = as.numeric(grepl("Muslim", relig))
                    , relig_LDS = as.numeric(grepl("Mormon", relig))
                    
                    , hh_n = ifelse(hh1 == '8 or more', 8, ifelse(hh1 == "Don't know/Refused", 2, as.numeric(hh1)))
                    
                    , income_under10 = as.numeric(income == 'Less than $10,000')
                    , income_10to20 = as.numeric(income == '10 to under $20,000')
                    , income_20to30 = as.numeric(income == '20 to under $30,000')
                    , income_30to40 = as.numeric(income == '30 to under $40,000')
                    , income_40to50 = as.numeric(income == '40 to under $50,000')
                    , income_50to75 = as.numeric(income == '50 to under $75,000')
                    , income_75to100 = as.numeric(income == '75 to under $100,000')
                    , income_100to150 = as.numeric(income == '100 to under $150,000')
                    , income_over150 = as.numeric(income == 'Over $150,000')
                    , income_refused = as.numeric(income == "(VOL) Don't know/Refused")
                    )]
# center and scale X
X_numeric = scale(X[, 2:ncol(X)])
# replace NA and NaN with 0
X_numeric = apply(X_numeric, 2, function(x) {
  x[is.na(x) | is.nan(x)] <- 0
  x
})
# create full covar matrix
X = data.frame(state = X$state, X_numeric)
##### Create test/training split
set.seed(123)
# train_ind = createDataPartition(X
#                                 , y = X$state
#                                 , p = .6, list = FALSE)
train_ind = sample.int(nrow(X), size = 1000, replace = F)
X_train = X[train_ind, ]
X_test = X[-train_ind, ]
Y_train = data_sept18[train_ind, .(state = as.character(state), y_dem = as.numeric(qsupport == '1-D'))]
Y_test = data_sept18[-train_ind, .(state = as.character(state), y_dem = as.numeric(qsupport == '1-D'))]
# create data that we actually observe
Y_train_agg = Y_train[, .(y_dem_pct = mean(y_dem), .N), by = state]
Y_train_agg

Mean embeddings

We observe bags of points \(\{x_j^i\}_{j = 1}^{N_i}\) from \(i = 1, \dots, n\), where \(x_j^i \in \mathbb{R}^p\). We have to embed the \(x_j^i\) in feature space and then take the mean. This means we can’t use the kernel trick which would take us directly from \(\mathbb{R}^p \times \mathbb{R}^p \to \mathbb{R}\). In order to calculate the coordinate of each observation in feature space, we convert each point to an explicit featurization: \(x_j^i \in \mathbb{R}\) is mapped to \[\phi(x_j^i) = [k(x_j^i, u_1), \dots, k(x_j^i, u_d)]^T \in \mathbb{R}^d\] where \(\mathbf{u} = \{u_l\}_{l = 1}^d\) are a set of landmark points. For now we’ll set \(d = 100\) and choose \(u_l\) using k-means clustering.

Specify landmark points \(\mathbf{u} = (u_1, \dots, u_k)\) as the centroids of k-means clustering

n_centers = 50
groups = kmeans(X_train[, -1], centers = n_centers)
u = as.matrix(groups$centers)
head(u)
      sex_male   sex_female          age educ_postgrad  educ_bach educ_assoc educ_highschool   educ_none        hisp
1  0.056526264 -0.056526264  0.136381670   -0.35356593  1.6547840 -0.3815408      -0.4857439 -0.23249882 -0.37662470
2  0.007386058 -0.007386058  0.450631837   -0.35356593 -0.6039640 -0.3815408      -0.4857439  4.29864489 -0.20827615
3  0.096731887 -0.096731887  0.002648315   -0.09914351  0.2995352 -0.3815408      -0.1805517 -0.23249882 -0.37662470
4  0.900844348 -0.900844348 -0.461239261    2.82671430 -0.6039640 -0.3815408      -0.4857439 -0.23249882  0.22943009
5 -0.163422145  0.163422145 -0.228312139   -0.16649062  0.8575788  0.1480471      -0.4857439  0.03403904 -0.02012188
6 -1.109436805  1.109436805  0.073345896   -0.35356593 -0.2275060  0.3186921       0.2772365 -0.23249882  0.22943009
   race_white race_black race_asian race_mixedother relig_protestant relig_catholic relig_athiest relig_jewish relig_muslim
1  0.42138314 -0.2660408 -0.1546641     -0.34741606        0.3562476    -0.48663987    -0.2112912   -0.1658855  -0.08297413
2  0.30174629 -0.2660408 -0.1546641      0.01082484        0.3383583    -0.34550787    -0.2112912   -0.1658855  -0.08297413
3 -1.77889449 -0.2660408 -0.1546641      2.87675206        0.6380055    -0.28340979    -0.2112912   -0.1658855  -0.08297413
4  0.09368222 -0.2660408 -0.1546641      0.29741756        1.1210189    -0.48663987    -0.2112912   -0.1658855  -0.08297413
5  0.01106854 -0.2660408  0.2345479      0.03189783       -0.8915370    -0.48663987    -0.2112912   -0.1658855  -0.08297413
6  0.40577833 -0.2660408 -0.1546641     -0.23994379        0.1147409    -0.06324387    -0.2112912   -0.1658855  -0.08297413
   relig_LDS       hh_n income_under10 income_10to20 income_20to30 income_30to40 income_40to50 income_50to75 income_75to100
1 -0.1447158  0.2753264    -0.20533514    -0.2745375    -0.3101534    -0.2967138   -0.26109503    -0.3815408     -0.3646904
2 -0.1447158 -0.2437303     1.48554672    -0.2745375     0.2786010     0.5177401   -0.03393199    -0.3815408     -0.1921804
3 -0.1447158  0.4115221    -0.20533514    -0.2745375    -0.3101534     0.2896930   -0.09753764    -0.2615009     -0.1162760
4 -0.1447158  0.5204786    -0.20533514    -0.2745375    -0.3101534    -0.2967138   -0.26109503    -0.3815408      2.7404888
5  6.9061577  0.5685476     0.09305578    -0.2745375    -0.1023577     0.3500584   -0.26109503     0.1480471      0.3659400
6 -0.1447158 -0.1151011    -0.20533514    -0.2745375     3.2223729    -0.2967138   -0.26109503    -0.3815408     -0.3646904
  income_100to150 income_over150 income_refused
1               0              0    -0.36669339
2               0              0    -0.02311422
3               0              0    -0.11931639
4               0              0    -0.36669339
5               0              0    -0.18479854
6               0              0    -0.36669339

Create RBF kernel and get embeddings of training set \(\phi(x)\) using kernel and landmark points \[\phi(x_i) = [k(x_i, u_1), \dots, k(x_i, u_k)]\]

Choose scale parameter \(\sigma\) for RBF kernel - use median heuristic for now

sigma

[1] 1.125302e-20

Calculate mean embeddings for each state

Model 1 - Frequentist

Normal LASSO regression on the kernel mean embeddings - no Bayesian treatment

# fit initial lasso to find significant covars
fit_lambda = cv.glmnet(x = as.matrix(mu_hat[, -1, with = F])
                       , y = Y_train_agg[order(state), ]$y_dem_pct
                       , nfolds = 10)

# get indicies of non-0 covars (except intercept)
ind = which(coef(fit_lambda, s = 'lambda.min')[-1] != 0)

# re-fit LASSO only with non-0 covars
fit = glmnet(x = as.matrix(mu_hat[, ind + 1, with = F])
             , y = Y_train_agg[order(state), ]$y_dem_pct)

Predict at the individual level

THINGS TO DO

parameter choice:

  • number of landmark points (how is this normally chosen?)
  • Calculate landmark points with full data set or just training?
  • scale parameter \(\sigma\) for RBF kernel (right now just usiing median heuristic)

Bags based on demos instead of state (more specific to this poll than most we’d be dealing with)?

Choose data set: * census microdata with actual county-level election outcomes. pro: large (like actual voterfile), con: outcomes not at the individual-level * Pew survey data. pro: outcomes at the individual-level, con: it’s small * census microdata for covar data with survey data for outomes. Pro: large covar data, closer to real scenario, con: can only link at the state-level, still no individual-level outcome data * synthetic data. pro: can make it exactly what we want, con: effort to synthesize

** benefit of the larger data set - more realistic, we’d really need the landmark points when we don’t if only working with the survey data

Compare against lasso/custom-built logit or maybe NN that has access to the individual-level outcomes (more realistic benchmark than)

**Implement full Bayesian treatment (uncertainty in mean embeddings as well as bag size)

MRP - standard for EI in political applications

LS0tCnRpdGxlOiAiQmF5ZXNpYW4gREIgUHJhY3RpY2UiCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCgpgYGB7cn0Kcm0obGlzdCA9IGxzKCkpCmxpYnJhcnkoZGF0YS50YWJsZSkKbGlicmFyeShmb3JlaWduKQpsaWJyYXJ5KGtlcm5sYWIpCmxpYnJhcnkoTUFTUykgICMgZm9yIG12cm5vcm0KbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KGdyaWRFeHRyYSkKbGlicmFyeShnbG1uZXQpCmxpYnJhcnkoY2FyZXQpCnNldHdkKCd+L2dpdGh1Yi9iZHIvJykKYGBgCgojIyBPdmVydmlldwoKQmF5ZXNpYW4gZGlzdHJpYnV0aW9uIHJlZ3Jlc3Npb24gKEJEUikgaXMgYnVpbHQgb24gYSBmZXcgcGllY2VzIG9mIHRoZW9yeToKCjEuIEtlcm5lbCBtZWFuIGVtYmVkZGluZ3MKMi4gR2F1c3NpYW4gcHJvY2VzcyByZWdyZXNzaW9uIChhcyB0aGUgcHJpb3IgZm9yIHRoZSBrZXJuZWwgbWVhbiBlbWJlZGRpbmdzKQozLiBMYW5kbWFyayBwb2ludHMgZm9yIGRpbWVuc2lvbmFsaXR5IHJlZHVjdGlvbiAoYWR2YW50YWdlcyBvZiB0aGlzIG92ZXIgRmFzdEZvb2Q/IGJvdGggYXJlIHJlZHVjaW5nIHRoZSBkaW1lbnNpb25hbGl0eSBvZiB0aGUgZmVhdHVyZSBlbWJlZGRpbmcgc28gdGhhdCB3ZSBjYW4gY2FsdWFsYXRlIHRoZSBlbXBpcmljYWwgbWVhbikKClRoaXMgbm90ZWJvb2sgYnVpbGRzIHRoZSB0aGVvcnkgb2YgQmF5ZXNpYW4gRGlzdHJpYnV0aW9uIFJlZ3Jlc3Npb24gcGllY2UgYnkgcGllY2U6CgoxLiBFeHBsb3JlIGtlcm5lbHMgZnJvbSB0aGUgYGtlcm5sYWJgIHBhY2thZ2UuICBXZSdsbCBsYXRlciB1c2UgdGhlIGZ1bmN0aW9ucyBmcm9tIHRoaXMgcGFja2FnZSB0byBjYWxjdWxhdGUgbWVhbiBlbWJlZGRpbmdzIGZvciBiYWdzIG9mIG9ic2VydmF0aW9ucyAkXHt4X2peaVx9X3tqPTF9XntOX2l9JC4KMi4gCgoKIyMgRXhwbG9yZSBLZXJuZWxzIGZyb20gYGtlcm5sYWJgIHBhY2thZ2UKCmBgYHtyfQojIyBjcmVhdGUgYSBSQkYga2VybmVsIGZ1bmN0aW9uIHdpdGggc2lnbWEgaHlwZXItcGFyYW1ldGVyIDAuMDUKcmJmID0gcmJmZG90KHNpZ21hID0gMSkKCiMjIGNyZWF0ZSBhcnRpZmljaWFsIGRhdGEgc2V0CnggPC0gbWF0cml4KHJub3JtKDYwKSwgNiwgMTApCgojIyBjb21wdXRlIGtlcm5lbCBtYXRyaXgKa3ggPC0ga2VybmVsTWF0cml4KHJiZiwgeCkgICMjIGtfMTIgaXMgZXF1aXZhbGVudCB0byBleHAoLSBzdW0oKHhbMSxdIC0geFsyLF0pXjIpKQpgYGAKCgojIyBCYXNpYyBHYXVzc2lhbiBwcm9jZXNzCgpBIEdhdXNzaWFuIHByb2Nlc3MgaXMgYSBjb2xsZWN0aW9uIG9mIHJhbmRvbSB2YXJpYWJsZXMsIGFueSBmaW5pdGUgc3Vic2V0IG9mIHdoaWNoIGZvbGxvd3MgYSBtdWx0aXZhcmlhdGUgbm9ybWFsIGRpc3RyaWJ1dGlvbgoKKnByaW9yKjogJGYgXHNpbSBcbWF0aGNhbHtHUH0oXG1hdGhiZnswfSwgayh4LCB4JykpJAoKV2UgZml4IGEgZmluaXRlIHNldCBvZiAkZCQgcG9pbnRzICRcbWF0aGJme3N9ID0gKHNfMSwgXGRvdHMsIHNfZCkkIGluIG9yZGVyIHRvIGRyYXcgZnJvbSB0aGUgR1AgYXMgYSBtdWx0aXZhcmlhdGUgbm9ybWFsLiBDb25kaXRpb25pbmcgb24gJHMkLCB0aGlzIGJlY29tZXMgJFxtYXRoYmZ7Zn0gXHNpbSBcbWF0aGNhbHtOfShcbWF0aGJmezB9X2QsIFxTaWdtYV9kKSQgd2hlcmUgJFxTaWdtYV9kJCBpcyB0aGUgZW1waXJpY2FsIGNvdmFyaWFuY2UgbWF0cml4IG9mIG91ciBwb2ludHMgJHMkLgoKV2UgdGhlbiBgYG9ic2VydmUiIDUgcG9pbnRzICRce3hfaSwgeV9pXH1fe2kgPSAxfV5uJC4gIFdlIGFzc3VtZSB0aGF0IHkgaXMgb2JzZXJ2ZWQgd2l0aG91dCBub2lzZSBzdWNoIHRoYXQgJHkgPSBmKHgpJC4gIEluIG9yZGVyIHRvIHByZWRpY3QgYXQgYSBuZXcgcG9pbnQgJHhfXHN0YXIkLCB3ZSBjb25kaWRpdG9uIG9uIHRoZSBvYnNlcnZlZCBwb2ludHMgJFgkIGFuZCB0aGVpciBhc3NvY2lhdGVkIG91dGNvbWVzICRZJCwgYW5kIGFycml2ZSBhdCB0aGUgY2xvc2VkLWZvcm0gcG9zdGVyaW9yIHByZWRpY3RpdmUgZGlzdHJpYnV0aW9uIG9mICRmX1xzdGFyJAoKKnBvc3Rlcmlvcio6ICRmX1xzdGFyIHwgeF9cc3RhciwgWCwgXG1hdGhiZnt5fSBcc2ltIFxtYXRoY2Fse059KGtfXHN0YXIgS157LTF9XG1hdGhiZnt5fSwga197XHN0YXJcc3Rhcn0gLSBrX1xzdGFyIEteey0xfWtfXHN0YXJeVCkkCgp3aGVyZSAkS197aWp9ID0gayh4X2ksIHhfaikkIGFuZCAka19cc3RhciA9IFtrKHhfMSwgeF9cc3RhciksIFxkb3RzLCBrKHhfbiwgeF9cc3RhcildJCBhbmQgJGtfe1xzdGFyXHN0YXJ9ID0gayh4X3N0YXIsIHhfc3RhcikkCgpgYGB7cn0KIyBkZWZpbmUgZnVuY3Rpb24gdG8gY2FsY3VsYXRlIGVtcGlyaWNhbCBjb3ZhcmlhbmNlIG1hdHJpeCBiYXNlZCBvbiBHYXVzc2lhbiBrZXJuZWwgd2l0aCBsZW5ndGgtc2NhbGUgbApjYWxjU2lnbWEgPSBmdW5jdGlvbih4MSwgeDIsIGwgPSAxKXsKICBTaWdtYSA9IG1hdHJpeChucm93ID0gbGVuZ3RoKHgxKSwgbmNvbCA9IGxlbmd0aCh4MikpCiAgCiAgZm9yKGkgaW4gMTpsZW5ndGgoeDEpKXsKICAgIGZvcihqIGluIDE6bGVuZ3RoKHgyKSl7CiAgICAgIFNpZ21hW2ksal0gPSBleHAoLTEvMiAqICgoeDFbaV0gLSB4MltqXSkvbCleMikKICAgIH0KICB9CiAgcmV0dXJuKFNpZ21hKQp9CgojIGRlZmluZSB0aGUgcG9pbnRzIHRoYXQgd2Ugd2FudCB0byBmaXggZm9yIHRoZSBmdW5jdGlvbiBkcmF3CnMgPSBzZXEoLTUsIDUsIGJ5ID0gMC4xKQoKIyBjYWxjdWxhdGUgdGhlIGVtcGlyaWNhbCBjb3ZhcmlhbmNlIG9mIHRoZSBwb2ludHMgKGJhc2ljYWxseSAwKQpTaWdtYSA9IGNhbGNTaWdtYShzLCBzKQoKIyBkcmF3IDUgc2FtcGxlcyBmcm9tIHRoZSBHUCBwcmlvciBhdCB0aGUgZml4ZWQgcG9pbnRzCnhfcHJpb3IgPSB0KG12cm5vcm0obiA9IDUsIG11ID0gcmVwKDAsIGxlbmd0aChzKSksIFNpZ21hID0gU2lnbWEpKQp4X2RyYXdzID0gZGF0YS5mcmFtZShjYmluZChzLCB4X3ByaW9yKSkKeF9kcmF3cyA9IG1lbHQoeF9kcmF3cywgaWQgPSAncycsIHZhbHVlLm5hbWUgPSAnZih4KScpCgojIHBsb3QgZHJhd3MgZnJvbSB0aGUgcHJpb3IKcGxvdF9ncF9wcmlvciA9IGdncGxvdCh4X2RyYXdzLCBhZXMoeCA9IHMsIHkgPSBgZih4KWAsIGNvbG9yID0gdmFyaWFibGUpKSArIGdlb21fbGluZSgpICsKICBnZ3RpdGxlKCJEcmF3cyBmcm9tIEdQIFByaW9yIikgKyB0aGVtZV9taW5pbWFsKCkKCiMgc3BlY2lmeSBwb2ludHMgdGhhdCB3ZSBvYnNlcnZlCnhfb2JzID0gYygtNCwgLTIuNSwgLTEsIDAsIDQpCnlfb2JzID0gYygtMiwgMCwgMSwgMiwgLTEpCgojIGNhbGN1bGF0ZSBrZXJuZWwgbWF0cmljaWVzIG5lZWRlZCBmb3IgcG9zdGVyaW9yIGV2YWx1YXRpb24KS194eCA9IGNhbGNTaWdtYSh4X29icywgeF9vYnMpCktfeHN0YXJ4ID0gY2FsY1NpZ21hKHMsIHhfb2JzKQpLX3h4c3RhciA9IGNhbGNTaWdtYSh4X29icywgcykKS194c3RhcnhzdGFyID0gY2FsY1NpZ21hKHMsIHMpCgojIGNhbGN1bGF0ZSBwb3N0ZXJpb3IgbWVhbiBhbmQgdmFyaWFuY2UKbXUgPSBLX3hzdGFyeCAlKiUgc29sdmUoS194eCkgJSolIHlfb2JzClNpZ21hX3N0YXIgPSBLX3hzdGFyeHN0YXIgLSBLX3hzdGFyeCAlKiUgc29sdmUoS194eCkgJSolIEtfeHhzdGFyCgojIGRyYXcgNSBzYW1wbGVzIGZyb20gdGhlIHBvc3RlcmlvciBhdCBmaXhlZCBldmFsIHBvaW50cyBzCnhfcG9zdCA9IHQobXZybm9ybSg1LCBtdSA9IG11LCBTaWdtYSA9IFNpZ21hX3N0YXIpKQp4X3Bvc3QgPSBkYXRhLmZyYW1lKGNiaW5kKHMsIHhfcG9zdCkpCnhfcG9zdCA9IG1lbHQoeF9wb3N0LCBpZCA9ICdzJywgdmFsdWUubmFtZSA9ICdmX3N0YXInKQoKIyBjYWxjdWxhdGUgOTUlIGNvbmZpZGVuY2UgYmFuZHMgZm9yIHBvc3RlcmlvcgpmX3N0YXJfY292YXIgPSBkYXRhLmZyYW1lKGNiaW5kKHMsIHViID0gbXUgKyAyICogc3FydChkaWFnKFNpZ21hX3N0YXIpKSwgbGIgPSBtdSAtIDIgKiBzcXJ0KGRpYWcoU2lnbWFfc3RhcikpKSkKCiMgcGxvdCBkcmF3cyBmcm9tIHBvc3RlcmlvcgpwbG90X2dwX3Bvc3QgPSBnZ3Bsb3QoKSArIAogIGdlb21fcmliYm9uKGRhdGEgPSBmX3N0YXJfY292YXIsIGFlcyh4ID0gcywgeW1pbiA9IFYzLCB5bWF4ID0gVjIpLCBmaWxsID0gImdyZXkiLCBhbHBoYSA9IDAuNSkgKwogIGdlb21fbGluZShkYXRhID0geF9wb3N0LCBhZXMoeCA9IHMsIHkgPSBmX3N0YXIsIGNvbG9yID0gdmFyaWFibGUpKSArCiAgI2dlb21fcG9pbnQoYWVzKHggPSB4X29icywgeSA9IHlfb2JzKSkgKwogIGdndGl0bGUoIkRyYXdzIGZyb20gR1AgUG9zdGVyaW9yIikgKwogIHRoZW1lX21pbmltYWwoKQogIApncmlkLmFycmFuZ2UocGxvdF9ncF9wcmlvciwgcGxvdF9ncF9wb3N0LCBucm93ID0gMSkKYGBgCgoKIyMgVHJ5IG91dCBCRFIgb24gc3VydmV5IGRhdGEKCipHb2FsKjogRXN0aW1hdGUgaW5kaXZpZHVhbC1sZXZlbCBzdXBwb3J0IHVzaW5nIEJEUiBvbiBzdGF0ZS1sZXZlbCBzdXBwb3J0IG91dGNvbWVzIAoKIyMjIERhdGEKCmBgYHtyfQpkYXRhX3NlcHQxOCA9IGRhdGEudGFibGUocmVhZC5zcHNzKCdkYXRhL1NlcHQxOC9TZXB0MTggcHVibGljLnNhdicsIHRvLmRhdGEuZnJhbWUgPSBUKSwgc3RyaW5nc0FzRmFjdG9ycyA9IEYpCmRhdGFfc2VwdDE4CmBgYAoKSW5kaXZpZHVhbC1sZXZlbCBzdXJ2ZXkgcmVzcG9uc2VzIChuID0gYG5yb3coZGF0YV9zZXB0MThgKSBmcm9tIFNlcHRlbWJlciAyMDE4IFBldyBSZXNlYXJjaCBzdXJ2ZXkgKGh0dHBzOi8vd3d3LnBlb3BsZS1wcmVzcy5vcmcvZGF0YXNldC9zZXB0ZW1iZXItMjAxOC1wb2xpdGljYWwtc3VydmV5LykuCgoKCiMjIyMgUmVjb2RlIHN1cnZleSByZXNwb25zZXMKClJlY29kZSB0aGUgc3VydmV5IHJlc3BvbnNlcyAtIGNvbWJpbmUgcTcgKHN0cm9uZykgYW5kIHE4IChsZWFuZXJzKSB0byBnZXQgZnVsbCBzdXBwb3J0IHJlc3BvbnNlCmBgYHtyfQojIyBzdXBwb3J0IApkYXRhX3NlcHQxOFssIC5OLCAuKHE3LCBxOCldCmRhdGFfc2VwdDE4WywgcXN1cHBvcnQgOj0gTlVMTF0KZGF0YV9zZXB0MThbcTcgPT0gIkRlbW9jcmF0aWMgUGFydHkncyBjYW5kaWRhdGUiIHwgcTggPT0gIkRlbW9jcmF0aWMgUGFydHkncyBjYW5kaWRhdGUiLCBxc3VwcG9ydCA6PSAnMS1EJ10KZGF0YV9zZXB0MThbcTcgPT0gIlJlcHVibGljYW4gUGFydHkncyBjYW5kaWRhdGUiIHwgcTggPT0gIlJlcHVibGljYW4gUGFydHkncyBjYW5kaWRhdGUiLCBxc3VwcG9ydCA6PSAnMi1SJ10KZGF0YV9zZXB0MThbcTggPT0gIihWT0wpIE90aGVyIiwgcXN1cHBvcnQgOj0gJzMtTyddCmRhdGFfc2VwdDE4W2lzLm5hKHFzdXBwb3J0KSwgcXN1cHBvcnQgOj0gJzQtREsvUiddCgpkYXRhX3NlcHQxOFssIC4oLk4sIHBjdCA9IC5OL25yb3coZGF0YV9zZXB0MTgpKSwgcXN1cHBvcnRdW29yZGVyKHFzdXBwb3J0KV0KYGBgCgojIGNhbGN1bGF0ZSBwZXJjZW50YWdlcyBieSBzdGF0ZQpgYGB7cn0KZGF0YV9zdGF0ZSA9IGRhdGFfc2VwdDE4WywgLih5X2RlbSA9IG1lYW4ocXN1cHBvcnQgPT0gJzEtRCcpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLCB5X3JlcCA9IG1lYW4ocXN1cHBvcnQgPT0gJzItUicpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLCB5X290aGVyID0gbWVhbihxc3VwcG9ydCA9PSAnMy1PJykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAsIHlfZGtyID0gbWVhbihxc3VwcG9ydCA9PSAnNC1ESy9SJykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAsIHRvdGFsX3Jlc3BvbmRlbnRzID0gLk4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIHNhbXBsZSBjb3ZhcmlhdGVzCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLCBhZ2VfdW5kZXIzMCA9IG1lYW4oYXMubnVtZXJpYyhhZ2UpIDwgMzApCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLCByYWNlX1cgPSBtZWFuKHJhY2VjbWIgPT0gJ1doaXRlJykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICApLCBieSA9IHNzdGF0ZV1bb3JkZXIoc3N0YXRlKV0KCmhlYWQoZGF0YV9zdGF0ZSkKYGBgCgojIENoZWNrIHJlbGF0aW9uc2hoaXAgYmV0d2VlbiBkZW0gdm90ZSBhbmQgJSB3aGl0ZSBieSBzdGF0ZQpgYGB7cn0KcGxvdCh5X2RlbSB+IHJhY2VfVwogICwgZGF0YSA9IGRhdGFfc3RhdGUKKQpgYGAKCgpgYGB7cn0KZGF0YV9zZXB0MTgKYGBgCgoKYGBge3J9CmRhdGFfc2VwdDE4WywgLk4sIGhoMV1bb3JkZXIoaGgxKV0KClggPSBkYXRhX3NlcHQxOFssIC4oc3RhdGUgPSBhcy5jaGFyYWN0ZXIoc3N0YXRlKQogICAgICAgICAgICAgICAgICAgICwgc2V4X21hbGUgPSBhcy5udW1lcmljKHNleCA9PSAnTWFsZScpCiAgICAgICAgICAgICAgICAgICAgLCBzZXhfZmVtYWxlID0gYXMubnVtZXJpYyhzZXggPT0gJ0ZlbWFsZScpCiAgICAgICAgICAgICAgICAgICAgLCBhZ2UgPSBhcy5udW1lcmljKGFnZSkKICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAsIGVkdWNfcG9zdGdyYWQgPSBhcy5udW1lcmljKGdyZXBsKCJQb3N0Z3JhZHVhdGUiLCBlZHVjKSkKICAgICAgICAgICAgICAgICAgICAsIGVkdWNfYmFjaCA9IGFzLm51bWVyaWMoZ3JlcGwoIkZvdXIgeWVhciIsIGVkdWMpKQogICAgICAgICAgICAgICAgICAgICwgZWR1Y19hc3NvYyA9IGFzLm51bWVyaWMoZ3JlcGwoIlR3byB5ZWFyIGFzc29jaWF0ZXxTb25lIGNvbGxlZ2UiLCBlZHVjKSkKICAgICAgICAgICAgICAgICAgICAsIGVkdWNfaGlnaHNjaG9vbCA9IGFzLm51bWVyaWMoZ3JlcGwoIkhpZ2ggc2Nob29sIGdyYWR1YXRlIiwgZWR1YykpCiAgICAgICAgICAgICAgICAgICAgLCBlZHVjX25vbmUgPSBhcy5udW1lcmljKGdyZXBsKCJMZXNzIHRoYW4gaGlnaCBzY2hvb2x8SGlnaCBzY2hvb2wgaW5jb21wbGV0ZSIsIGVkdWMpKQogICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICwgaGlzcCA9IGFzLm51bWVyaWMoaGlzcCA9PSAnWWVzJykKICAgICAgICAgICAgICAgICAgICAsIHJhY2Vfd2hpdGUgPSBhcy5udW1lcmljKHJhY2VjbWIgPT0gJ1doaXRlJykKICAgICAgICAgICAgICAgICAgICAsIHJhY2VfYmxhY2sgPSBhcy5udW1lcmljKHJhY2VjbWIgPT0gJ0JsYWNrIG9yIEFmcmljYW4tQW1lcmljYW4nKQogICAgICAgICAgICAgICAgICAgICwgcmFjZV9hc2lhbiA9IGFzLm51bWVyaWMocmFjZWNtYiA9PSAnQXNpYW4gb3IgQXNpYW4tQW1lcmljYW4nKQogICAgICAgICAgICAgICAgICAgICwgcmFjZV9taXhlZG90aGVyID0gYXMubnVtZXJpYyhyYWNlY21iID09ICdNaXhlZCBSYWNlJyB8IHJhY2VjbWIgPT0gJ09yIHNvbWUgb3RoZXIgcmFjZScpCiAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgLCByZWxpZ19wcm90ZXN0YW50ID0gYXMubnVtZXJpYyhncmVwbCgiUHJvdGVzdGFudHxDaHJpc3RpYW4iLCByZWxpZykpCiAgICAgICAgICAgICAgICAgICAgLCByZWxpZ19jYXRob2xpYyA9IGFzLm51bWVyaWMoZ3JlcGwoIkNhdGhvbGljIiwgcmVsaWcpKQogICAgICAgICAgICAgICAgICAgICwgcmVsaWdfYXRoaWVzdCA9IGFzLm51bWVyaWMoZ3JlcGwoIkF0aGllc3R8QWdub3N0aWMiLCByZWxpZykpCiAgICAgICAgICAgICAgICAgICAgLCByZWxpZ19qZXdpc2ggPSBhcy5udW1lcmljKGdyZXBsKCJKZXdpc2giLCByZWxpZykpCiAgICAgICAgICAgICAgICAgICAgLCByZWxpZ19tdXNsaW0gPSBhcy5udW1lcmljKGdyZXBsKCJNdXNsaW0iLCByZWxpZykpCiAgICAgICAgICAgICAgICAgICAgLCByZWxpZ19MRFMgPSBhcy5udW1lcmljKGdyZXBsKCJNb3Jtb24iLCByZWxpZykpCiAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgLCBoaF9uID0gaWZlbHNlKGhoMSA9PSAnOCBvciBtb3JlJywgOCwgaWZlbHNlKGhoMSA9PSAiRG9uJ3Qga25vdy9SZWZ1c2VkIiwgMiwgYXMubnVtZXJpYyhoaDEpKSkKICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAsIGluY29tZV91bmRlcjEwID0gYXMubnVtZXJpYyhpbmNvbWUgPT0gJ0xlc3MgdGhhbiAkMTAsMDAwJykKICAgICAgICAgICAgICAgICAgICAsIGluY29tZV8xMHRvMjAgPSBhcy5udW1lcmljKGluY29tZSA9PSAnMTAgdG8gdW5kZXIgJDIwLDAwMCcpCiAgICAgICAgICAgICAgICAgICAgLCBpbmNvbWVfMjB0bzMwID0gYXMubnVtZXJpYyhpbmNvbWUgPT0gJzIwIHRvIHVuZGVyICQzMCwwMDAnKQogICAgICAgICAgICAgICAgICAgICwgaW5jb21lXzMwdG80MCA9IGFzLm51bWVyaWMoaW5jb21lID09ICczMCB0byB1bmRlciAkNDAsMDAwJykKICAgICAgICAgICAgICAgICAgICAsIGluY29tZV80MHRvNTAgPSBhcy5udW1lcmljKGluY29tZSA9PSAnNDAgdG8gdW5kZXIgJDUwLDAwMCcpCiAgICAgICAgICAgICAgICAgICAgLCBpbmNvbWVfNTB0bzc1ID0gYXMubnVtZXJpYyhpbmNvbWUgPT0gJzUwIHRvIHVuZGVyICQ3NSwwMDAnKQogICAgICAgICAgICAgICAgICAgICwgaW5jb21lXzc1dG8xMDAgPSBhcy5udW1lcmljKGluY29tZSA9PSAnNzUgdG8gdW5kZXIgJDEwMCwwMDAnKQogICAgICAgICAgICAgICAgICAgICwgaW5jb21lXzEwMHRvMTUwID0gYXMubnVtZXJpYyhpbmNvbWUgPT0gJzEwMCB0byB1bmRlciAkMTUwLDAwMCcpCiAgICAgICAgICAgICAgICAgICAgLCBpbmNvbWVfb3ZlcjE1MCA9IGFzLm51bWVyaWMoaW5jb21lID09ICdPdmVyICQxNTAsMDAwJykKICAgICAgICAgICAgICAgICAgICAsIGluY29tZV9yZWZ1c2VkID0gYXMubnVtZXJpYyhpbmNvbWUgPT0gIihWT0wpIERvbid0IGtub3cvUmVmdXNlZCIpCiAgICAgICAgICAgICAgICAgICAgKV0KCiMgY2VudGVyIGFuZCBzY2FsZSBYClhfbnVtZXJpYyA9IHNjYWxlKFhbLCAyOm5jb2woWCldKQoKIyByZXBsYWNlIE5BIGFuZCBOYU4gd2l0aCAwClhfbnVtZXJpYyA9IGFwcGx5KFhfbnVtZXJpYywgMiwgZnVuY3Rpb24oeCkgewogIHhbaXMubmEoeCkgfCBpcy5uYW4oeCldIDwtIDAKICB4Cn0pCiMgY3JlYXRlIGZ1bGwgY292YXIgbWF0cml4ClggPSBkYXRhLmZyYW1lKHN0YXRlID0gWCRzdGF0ZSwgWF9udW1lcmljKQoKCiMjIyMjIENyZWF0ZSB0ZXN0L3RyYWluaW5nIHNwbGl0CnNldC5zZWVkKDEyMykKIyB0cmFpbl9pbmQgPSBjcmVhdGVEYXRhUGFydGl0aW9uKFgKIyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICwgeSA9IFgkc3RhdGUKIyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICwgcCA9IC42LCBsaXN0ID0gRkFMU0UpCgp0cmFpbl9pbmQgPSBzYW1wbGUuaW50KG5yb3coWCksIHNpemUgPSAxMDAwLCByZXBsYWNlID0gRikKClhfdHJhaW4gPSBYW3RyYWluX2luZCwgXQpYX3Rlc3QgPSBYWy10cmFpbl9pbmQsIF0KCllfdHJhaW4gPSBkYXRhX3NlcHQxOFt0cmFpbl9pbmQsIC4oc3RhdGUgPSBhcy5jaGFyYWN0ZXIoc3RhdGUpLCB5X2RlbSA9IGFzLm51bWVyaWMocXN1cHBvcnQgPT0gJzEtRCcpKV0KWV90ZXN0ID0gZGF0YV9zZXB0MThbLXRyYWluX2luZCwgLihzdGF0ZSA9IGFzLmNoYXJhY3RlcihzdGF0ZSksIHlfZGVtID0gYXMubnVtZXJpYyhxc3VwcG9ydCA9PSAnMS1EJykpXQoKIyBjcmVhdGUgZGF0YSB0aGF0IHdlIGFjdHVhbGx5IG9ic2VydmUKWV90cmFpbl9hZ2cgPSBZX3RyYWluWywgLih5X2RlbV9wY3QgPSBtZWFuKHlfZGVtKSwgLk4pLCBieSA9IHN0YXRlXQoKWV90cmFpbl9hZ2cKYGBgCgojIyBNZWFuIGVtYmVkZGluZ3MKCldlIG9ic2VydmUgYmFncyBvZiBwb2ludHMgJFx7eF9qXmlcfV97aiA9IDF9XntOX2l9JCBmcm9tICRpID0gMSwgXGRvdHMsIG4kLCB3aGVyZSAkeF9qXmkgXGluIFxtYXRoYmJ7Un1ecCQuICBXZSBoYXZlIHRvIGVtYmVkIHRoZSAkeF9qXmkkIGluIGZlYXR1cmUgc3BhY2UgYW5kIHRoZW4gdGFrZSB0aGUgbWVhbi4gIFRoaXMgbWVhbnMgd2UgY2FuJ3QgdXNlIHRoZSBrZXJuZWwgdHJpY2sgd2hpY2ggd291bGQgdGFrZSB1cyBkaXJlY3RseSBmcm9tICRcbWF0aGJie1J9XnAgXHRpbWVzIFxtYXRoYmJ7Un1ecCBcdG8gXG1hdGhiYntSfSQuICBJbiBvcmRlciB0byBjYWxjdWxhdGUgdGhlIGNvb3JkaW5hdGUgb2YgZWFjaCBvYnNlcnZhdGlvbiBpbiBmZWF0dXJlIHNwYWNlLCB3ZSBjb252ZXJ0IGVhY2ggcG9pbnQgdG8gYW4gKmV4cGxpY2l0KiBmZWF0dXJpemF0aW9uOiAgJHhfal5pIFxpbiBcbWF0aGJie1J9JCBpcyBtYXBwZWQgdG8gJCRccGhpKHhfal5pKSA9IFtrKHhfal5pLCB1XzEpLCBcZG90cywgayh4X2peaSwgdV9kKV1eVCBcaW4gXG1hdGhiYntSfV5kJCQKd2hlcmUgJFxtYXRoYmZ7dX0gPSBce3VfbFx9X3tsID0gMX1eZCQgYXJlIGEgc2V0IG9mIGxhbmRtYXJrIHBvaW50cy4gIEZvciBub3cgd2UnbGwgc2V0ICRkID0gMTAwJCBhbmQgY2hvb3NlICR1X2wkIHVzaW5nIGstbWVhbnMgY2x1c3RlcmluZy4KCgpTcGVjaWZ5IGxhbmRtYXJrIHBvaW50cyAkXG1hdGhiZnt1fSA9ICh1XzEsIFxkb3RzLCB1X2spJCBhcyB0aGUgY2VudHJvaWRzIG9mIGstbWVhbnMgY2x1c3RlcmluZwoKYGBge3J9Cm5fY2VudGVycyA9IDUwCmdyb3VwcyA9IGttZWFucyhYX3RyYWluWywgLTFdLCBjZW50ZXJzID0gbl9jZW50ZXJzKQp1ID0gYXMubWF0cml4KGdyb3VwcyRjZW50ZXJzKQpoZWFkKHUpCmBgYAoKCkNyZWF0ZSBSQkYga2VybmVsIGFuZCBnZXQgZW1iZWRkaW5ncyBvZiB0cmFpbmluZyBzZXQgJFxwaGkoeCkkIHVzaW5nIGtlcm5lbCBhbmQgbGFuZG1hcmsgcG9pbnRzCiQkXHBoaSh4X2kpID0gW2soeF9pLCB1XzEpLCBcZG90cywgayh4X2ksIHVfayldJCQKCkNob29zZSBzY2FsZSBwYXJhbWV0ZXIgJFxzaWdtYSQgZm9yIFJCRiBrZXJuZWwgLSB1c2UgbWVkaWFuIGhldXJpc3RpYyBmb3Igbm93CmBgYHtyfQpyYmYxID0gcmJmZG90KHNpZ21hID0gMSkKCktfc2lnbWEgPSBrZXJuZWxNYXRyaXgocmJmMSwgeCA9IGFzLm1hdHJpeChYX3RyYWluWywgLTFdKSwgeSA9IHUpCmRpbShLX3NpZ21hKQpzaWdtYSA9IG1lZGlhbihLX3NpZ21hKQpgYGAKCgpgYGB7cn0KcmJmID0gcmJmZG90KHNpZ21hID0gMC4xKQpwaGlfeCA9IGtlcm5lbE1hdHJpeChyYmYsIHggPSBhcy5tYXRyaXgoWF90cmFpblssIC0xXSksIHkgPSB1KQpwaGlfeCA9IGRhdGEudGFibGUoc3RhdGUgPSBYX3RyYWluJHN0YXRlLCBwaGlfeCkKc2V0bmFtZXMocGhpX3gsIGMoJ3N0YXRlJywgcGFzdGUwKCd1JywgMTpuX2NlbnRlcnMpKSkKCmhlYWQocGhpX3gpCmBgYAoKQ2FsY3VsYXRlIG1lYW4gZW1iZWRkaW5ncyBmb3IgZWFjaCBzdGF0ZQoKYGBge3J9Cm11X2hhdCA9IHBoaV94WywgbGFwcGx5KC5TRCwgbWVhbiksIC5TRGNvbHMgPSBuYW1lcyhwaGlfeClbMjpuY29sKHBoaV94KV0sIGJ5ID0gc3RhdGVdW29yZGVyKHN0YXRlKV0KbXVfaGF0CmBgYAoKIyMjIE1vZGVsIDEgLSBGcmVxdWVudGlzdApOb3JtYWwgTEFTU08gcmVncmVzc2lvbiBvbiB0aGUga2VybmVsIG1lYW4gZW1iZWRkaW5ncyAtIG5vIEJheWVzaWFuIHRyZWF0bWVudAoKYGBge3J9CiMgZml0IGluaXRpYWwgbGFzc28gdG8gZmluZCBzaWduaWZpY2FudCBjb3ZhcnMKZml0X2xhbWJkYSA9IGN2LmdsbW5ldCh4ID0gYXMubWF0cml4KG11X2hhdFssIC0xLCB3aXRoID0gRl0pCiAgICAgICAgICAgICAgICAgICAgICAgLCB5ID0gWV90cmFpbl9hZ2dbb3JkZXIoc3RhdGUpLCBdJHlfZGVtX3BjdAogICAgICAgICAgICAgICAgICAgICAgICwgbmZvbGRzID0gMTApCgojIGdldCBpbmRpY2llcyBvZiBub24tMCBjb3ZhcnMgKGV4Y2VwdCBpbnRlcmNlcHQpCmluZCA9IHdoaWNoKGNvZWYoZml0X2xhbWJkYSwgcyA9ICdsYW1iZGEubWluJylbLTFdICE9IDApCgojIHJlLWZpdCBMQVNTTyBvbmx5IHdpdGggbm9uLTAgY292YXJzCmZpdCA9IGdsbW5ldCh4ID0gYXMubWF0cml4KG11X2hhdFssIGluZCArIDEsIHdpdGggPSBGXSkKICAgICAgICAgICAgICwgeSA9IFlfdHJhaW5fYWdnW29yZGVyKHN0YXRlKSwgXSR5X2RlbV9wY3QpCmBgYAoKCiBQcmVkaWN0IGF0IHRoZSBpbmRpdmlkdWFsIGxldmVsCiAKYGBge3J9CiMgZ2V0IGVtYmVkZGluZ3Mgb2YgdGVzdCBwb2ludHMKcGhpX3hfdGVzdCA9IGtlcm5lbE1hdHJpeChyYmYsIHggPSBhcy5tYXRyaXgoWF90ZXN0WywgLTFdKSwgeSA9IHUpCnBoaV94X3Rlc3QgPSBkYXRhLnRhYmxlKHN0YXRlID0gWF90ZXN0JHN0YXRlLCBwaGlfeF90ZXN0KQpzZXRuYW1lcyhwaGlfeF90ZXN0LCBjKCdzdGF0ZScsIHBhc3RlMCgndScsIDE6bl9jZW50ZXJzKSkpCgp5X2hhdCA9IHByZWRpY3QoZml0LCBuZXd4ID0gYXMubWF0cml4KFhfdGVzdFssIGluZCArIDFdKSwgcz0gMCkKeV9oYXQgPSBjYmluZChtdV9oYXRfZ2VuZGVyWywuKHN0YXRlLHNleCldLCB5X2hhdCA9IHlfaGF0KQoKeV9hY3R1YWwgPSBkYXRhX3NlcHQxOFssIC4oeV9kZW0gPSBtZWFuKGFzLm51bWVyaWMocXN1cHBvcnQgPT0gJzEtRCcpKSksIGJ5ID0gLihzc3RhdGUsc2V4KV0Kc2V0bmFtZXMoeV9hY3R1YWwsIGMoJ3N0YXRlJywgJ3NleCcsICd5X2RlbScpKQp5X2hhdCA9IG1lcmdlKHlfYWN0dWFsLCB5X2hhdCwgYnkgPSBjKCdzdGF0ZScsJ3NleCcpLCBhbGwgPSBUKQoKcGxvdCh5X2hhdCR5X2hhdC4xIH4geV9oYXQkeV9kZW0sIGNvbCA9IHlfaGF0JHNleCkKYGBgCgoKCgojIyBUSElOR1MgVE8gRE8KCipwYXJhbWV0ZXIgY2hvaWNlKjoKCi0gbnVtYmVyIG9mIGxhbmRtYXJrIHBvaW50cyAoaG93IGlzIHRoaXMgbm9ybWFsbHkgY2hvc2VuPykKLSBDYWxjdWxhdGUgbGFuZG1hcmsgcG9pbnRzIHdpdGggZnVsbCBkYXRhIHNldCBvciBqdXN0IHRyYWluaW5nPwotIHNjYWxlIHBhcmFtZXRlciAkXHNpZ21hJCBmb3IgUkJGIGtlcm5lbCAocmlnaHQgbm93IGp1c3QgdXNpaW5nIG1lZGlhbiBoZXVyaXN0aWMpCgpCYWdzIGJhc2VkIG9uIGRlbW9zIGluc3RlYWQgb2Ygc3RhdGUgKG1vcmUgc3BlY2lmaWMgdG8gdGhpcyBwb2xsIHRoYW4gbW9zdCB3ZSdkIGJlIGRlYWxpbmcgd2l0aCk/CgoqQ2hvb3NlIGRhdGEgc2V0KjoKKiBjZW5zdXMgbWljcm9kYXRhIHdpdGggYWN0dWFsIGNvdW50eS1sZXZlbCBlbGVjdGlvbiBvdXRjb21lcy4gcHJvOiBsYXJnZSAobGlrZSBhY3R1YWwgdm90ZXJmaWxlKSwgY29uOiBvdXRjb21lcyBub3QgYXQgdGhlIGluZGl2aWR1YWwtbGV2ZWwKKiBQZXcgc3VydmV5IGRhdGEuIHBybzogb3V0Y29tZXMgYXQgdGhlIGluZGl2aWR1YWwtbGV2ZWwsIGNvbjogaXQncyBzbWFsbAoqIGNlbnN1cyBtaWNyb2RhdGEgZm9yIGNvdmFyIGRhdGEgd2l0aCBzdXJ2ZXkgZGF0YSBmb3Igb3V0b21lcy4gIFBybzogbGFyZ2UgY292YXIgZGF0YSwgY2xvc2VyIHRvIHJlYWwgc2NlbmFyaW8sIGNvbjogY2FuIG9ubHkgbGluayBhdCB0aGUgc3RhdGUtbGV2ZWwsIHN0aWxsIG5vIGluZGl2aWR1YWwtbGV2ZWwgb3V0Y29tZSBkYXRhCiogc3ludGhldGljIGRhdGEuIHBybzogY2FuIG1ha2UgaXQgZXhhY3RseSB3aGF0IHdlIHdhbnQsIGNvbjogZWZmb3J0IHRvIHN5bnRoZXNpemUKCioqIGJlbmVmaXQgb2YgdGhlIGxhcmdlciBkYXRhIHNldCAtIG1vcmUgcmVhbGlzdGljLCB3ZSdkIHJlYWxseSBuZWVkIHRoZSBsYW5kbWFyayBwb2ludHMgd2hlbiB3ZSBkb24ndCBpZiBvbmx5IHdvcmtpbmcgd2l0aCB0aGUgc3VydmV5IGRhdGEKCkNvbXBhcmUgYWdhaW5zdCBsYXNzby9jdXN0b20tYnVpbHQgbG9naXQgb3IgbWF5YmUgTk4gdGhhdCBoYXMgYWNjZXNzIHRvIHRoZSBpbmRpdmlkdWFsLWxldmVsIG91dGNvbWVzIChtb3JlIHJlYWxpc3RpYyBiZW5jaG1hcmsgdGhhbikKCioqSW1wbGVtZW50IGZ1bGwgQmF5ZXNpYW4gdHJlYXRtZW50ICh1bmNlcnRhaW50eSBpbiBtZWFuIGVtYmVkZGluZ3MgYXMgd2VsbCBhcyBiYWcgc2l6ZSkKCk1SUCAtIHN0YW5kYXJkIGZvciBFSSBpbiBwb2xpdGljYWwgYXBwbGljYXRpb25zCgoKCgoKCgoKCg==